typedef struct Stack
{
	char* arr;
	int top;
	int capcity;
}ST;

void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps,char x);
void StackPop(ST* ps);
void StackPrint(ST ps);
int  StackTop(ST* ps);
int  StackSize(ST* ps);
bool  StackEmpty(ST* ps);

void StackInit(ST* ps)
{
	ps->arr = (char*)malloc(sizeof(char) * 4);
	if (ps->arr == NULL)
	{
		printf("malloc fail!");
		exit(-1);
	}
	ps->top = 0;
	ps->capcity = 4;
}
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->arr);
}
void StackPush(ST* ps, char x)
{
	assert(ps);
	if (ps->capcity == ps->top)
	{
		char* newdata = (char*)realloc(ps->arr, ps->capcity * 2 * sizeof(char));
		if (newdata)
		{
			ps->arr = newdata;
			ps->capcity = ps->capcity * 2;
		}
		else
		{
			printf("realloc fail!");
			return;
		}
	}
	ps->arr[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top>0);
	if (ps->capcity == ps->top)
	{
		char* newdata = (char*)realloc(ps->arr, ps->capcity * 2 * sizeof(char));
		if (newdata)
		{
			ps->arr = newdata;
			ps->capcity = ps->capcity * 2;
		}
		else
		{
			printf("realloc fail!");
			return;
		}
	}

	int tmp = ps->arr[ps->top - 1];
	tmp = ps->arr[ps->top];
	ps->top--;
}
int  StackTop(ST* ps)
{
	assert(ps);
    assert(ps->top>0);
    
	return ps->arr[ps->top-1];
}
int  StackSize(ST* ps)
{
	return ps->arr[ps->top];
}
bool  StackEmpty(ST* ps)
{
	assert(ps);

	if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}
void StackPrint(ST ps)
{
	int i = 0;
	for (i = 0; i < ps.top; i++)
	{
		printf("%d ", ps.arr[i]);
	}
	printf("\n");
}
bool isValid(char * s)
{
    ST stack;
    StackInit(&stack);
    while(*s != '\0')
    {
        if(*s == '[' || *s == '(' || *s == '{')
        {
            StackPush(&stack,*s);
            s++;
        }
        else
        {
            if(StackEmpty(&stack))
            {
                StackDestory(&stack);
                return false;
            }
            char temp = StackTop(&stack);
            StackPop(&stack);
            if((*s == '}' && temp != '{')
            || (*s == ')' && temp != '(')
            || (*s == ']' && temp != '['))
            {
                StackDestory(&stack);
                return false;
            }
            else //匹配
            {
                ++s;
            }
        }
    }
    bool ret = StackEmpty(&stack);
    StackDestory(&stack);
    return ret;
}